package com.fr.lintcode;

import java.util.Stack;

/**
*作者：furong
*日期：2017年2月24日
*时间：下午2:25:10
*/
public class Q203 {
    /**
     *@param root, index, value: The root of segment tree and 
     *@ change the node's value with [index, index] to the new given value
     *@return: void
     */
    public void modify(SegmentTreeNode root, int index, int value) {
        if (root == null || root.start > index || root.end < index) {
            return;
        }
        SegmentTreeNode cur = root;
        Stack<SegmentTreeNode> s = new Stack<>();
        while (cur != null) {
            if (cur.start == index && cur.end == index) {
                cur.max = value;
                break;
            }
            s.push(cur);
            if ((cur.start + cur.end) / 2 >= index) {
                cur = cur.left;
            } else {
                cur = cur.right;
            }
        }
        while (!s.empty()) {
            SegmentTreeNode st = s.pop();
            st.max = Math.max(st.left.max, st.right.max);
        }
    }
}
